# -*- coding: utf-8 -*-

"""剑指 Offer II 087. 复原 IP 
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：
输入：s = "0000"
输出：["0.0.0.0"]

示例 3：
输入：s = "1111"
输出：["1.1.1.1"]

示例 4：
输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]

示例 5：
输入：s = "10203040"
输出：["10.20.30.40","102.0.30.40","10.203.0.40"]

提示：
0 <= s.length <= 3000
s 仅由数字组成"""


class Solution:
    """数学上还是排列组合的问题，用回溯+递归
    在每个位置，以该位置为起点找[0:255]之间的有效数字时，可以用正则表达式，此处上下回调用之间的材料源完全可以用指针实现。
    同时为了节约空间，可以用状态表表示[0:255]，回溯时查表更方便
    
    本题难点在于状态表的建立"""
    @staticmethod
    def gen_ip_fragment():
        ip_fragment = {
            '0': dict(),
            '1': dict([(str(i), set([str(j) for j in range(10)])) for i in range(10)]),
            }

        ip_fragment.update({'2': dict([(str(i), set([str(j) for j in range(10)])) for i in range(5)]+[('5', set([str(k) for k in range(6)])),])})

        ip_fragment['2'].update([(str(i), set()) for i in range(6, 10)])

        for i in range(3, 10):
            ip_fragment.update({str(i): dict([(str(j), set()) for j in range(10)])})
        return ip_fragment

    def restoreIpAddresses(self, s: str):
        ip_fragment = self.gen_ip_fragment()
        answer, hi = [], len(s)
        def fork(start, group):
            if len(group) > 4:
                return
            if start < hi and (s[start] not in ip_fragment):
                return
            if start == hi:
                if len(group) == 4:
                    answer.append('.'.join(group))
                return
            
            group_new = group.copy()
            group_new.append(s[start])
            fork(start+1, group_new)

            if (second:= start+1) < hi:
                if s[second] in ip_fragment[s[start]]:
                    group_new = group.copy()
                    group_new.append(s[start:second+1])
                    fork(second+1, group_new)

                    if (third:= second+1) < hi:
                        if s[third] in ip_fragment[s[start]][s[second]]:
                            group_new = group.copy()
                            group_new.append(s[start:third+1])
                            fork(third+1, group_new)
        fork(0, [])
        return answer


if __name__ == '__main__':
    so = Solution()
    print(so.restoreIpAddresses(s = "25525511135"))
    print(so.restoreIpAddresses(s = "0000"))
    print(so.restoreIpAddresses(s = "1111"))
    print(so.restoreIpAddresses(s = "010010"))
    print(so.restoreIpAddresses(s = "10203040"))
    print(so.restoreIpAddresses(s = "28576"))

